from typing import *
from sortedcontainers import SortedDict


class Solution:

    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int,
                                      t: int) -> bool:
        sd = SortedDict()

        for i, v in enumerate(nums):
            if i > k:
                o = nums[i - k - 1]
                sd[o] -= 1
                if sd[o] == 0:
                    sd.pop(o)
            l = sd.bisect_left(v - t)
            r = sd.bisect_right(v + t) - 1
            if l <= r:
                return True
            sd[v] = sd.get(v, 0) + 1

        return False


sd = SortedDict()
sd['2'] = 20
sd['1'] = 100
print(sd)